lcmefandomcom_ru-20200213-history
Польская запись
Польская запись - это альтернативный способ записи арифметических выражений, преимущество которого состоит в отсутствии скобок. Существует два типа польской записи: прямая и обратная, также известные как префиксная и постфиксная. Отличие их от классического, инфиксного способа заключается в том, что знаки операций пишутся не между, а, соответственно, до или после аргументов. Прямая польская запись Сразу приведём примеры выражений, записанных таким образом: * + 3 5 7 ((3 + 5) * 7) + * 3 5 7 ((3 * 5) + 7) + 3 * 5 7 (3 + (5 * 7)) * 3 + 5 7 (3 * (5 + 7)) Хотя код для разбора прямой записи получается существенно короче, но, тем не менее, понять его несколько сложнее. let count_str s = let int_of_ascii x = int_of_char x - 48 and s = s ^ ";" and i = ref 0 in let parse_num () = let rec pn acc = match s.!i with '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x)) |_ -> acc in pn 0 in let rec parse () = match s.!i with '0'..'9' -> parse_num () |' ' -> incr i; parse () |'+' -> incr i; let fst = parse () in fst + parse () |'-' -> incr i; let fst = parse () in fst - parse () |'*' -> incr i; let fst = parse () in fst * parse () |'/' -> incr i; let fst = parse () in fst / parse () |';' -> failwith "End of line reached unexpectedly" | _ -> failwith "Unexpected symbol" in let result = parse () in if s.!i <> ';' then failwith "?!!" else result Итак, функция parse () пытается разобрать наименьший корректный кусок строки. Полагаю, дальнейшие комментарии излишни: в коде не так уж сложно разобраться. Обратная польская запись Несколько примеров: 3 5 + 7 * ((3 + 5) * 7) 3 5 * 7 + ((3 * 5) + 7) 3 5 7 * + (3 + (5 * 7)) 3 5 7 + * (3 * (5 + 7)) Обратная польская запись представляется более простой для понимания, но более сложной для реализации, нежели прямая. let count_rev s = let stack = ref [] in let push x = stack := x::!stack and pop () = match !stack with | l1::ls -> stack := ls; l1 | [] -> failwith "Stack underflow" and int_of_ascii x = int_of_char x - 48 and s = s ^ ";" and i = ref 0 in let parse_num () = let rec pn acc = match s.!i with '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x)) |_ -> acc in pn 0 in let rec parse () = match s.!i with '0'..'9' -> push (parse_num ()); parse () |' ' -> incr i; parse () |'+' -> push (pop () + pop ()); incr i; parse () |'-' -> let snd = pop () in push (pop () - snd); incr i; parse () |'*' -> push (pop () * pop ()); incr i; parse () |'/' -> let snd = pop () in push (pop () / snd); incr i; parse () | _ -> pop () in parse () Следует обратить внимание, что ключевым моментом в реализации разбора обратной польской записи является использование стека. Преобразование инфиксной записи в постфиксную Существует также алгоритм преобразования инфиксной записи в постфиксную с использованием стека и приоритета операций. Он весьма нетривиален, поэтому объяснять, что это такое, я буду сразу на примерах с кодом. let priority = function | "(" -> 0 | "+" | "-" -> 1 | "*" | "/" -> 2 | _ -> failwith "Undeclared identifier" Как нетрудно заметить, эта функция сопоставляет знакам различных операций приоритеты этих операций. Назначение приоритета скобки будет объяснено позднее. Для работы понадобится стек, а его проще всего представить списком: let stack = ref [] А теперь начинается самое интересное. Введём некоторые специальные функции для работы со стеком: let rec push x = (* эта функция кладёт новый элемент в стек очень хитрым образом *) match !stack with | [] -> stack := x; "" (* если стек пуст, просто запихать в него элемент *) | l1::ls -> if (priority x) > (priority l1) then (stack := x::!stack; "") (* то же самое, если новый элемент обладает более *) else (* высоким приоритетом, чем уже лежащий в стеке *) (stack := ls; l1 ^ " " ^ (push x)) (* а иначе - поиск места, где приоритет нового элемента превысит приоритет уже находящихся в стеке *) let pop_all () = let u = List.fold_left (fun x y -> x ^ y ^ " ") "" !stack in stack := []; u (* свёртка и очистка стека *) let add_bracket () = stack := "("::!stack (* просто добавление скобки методом заталкивания*) let rec rem_bracket () = match !stack with | [] -> failwith "unmatched closing bracket detected" | l1::ls -> stack := ls; if l1 = "(" then "" else (l1 ^ " " ^ (rem_bracket ())) (* что-то вроде pop_all (), но только до ближайшей скобки *) Фактически, код выше - это основная часть проблемы; теперь осталось совсем немного. let postfix_of_infix s = let s = s ^ ";" and i = ref 0 and int_of_ascii x = int_of_char x - 48 in let parse_num () = let rec pn acc = match s.!i with '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x)) |_ -> acc in pn 0 in let rec parse () = match s.!i with '0'..'9' -> let u = (string_of_int (parse_num ())) in u ^ " " ^ parse () |' ' -> incr i; parse () |'+' -> incr i; let u = (push "+") in u ^ parse () |'-' -> incr i; let u = (push "-") in u ^ parse () |'*' -> incr i; let u = (push "*") in u ^ parse () |'/' -> incr i; let u = (push "/") in u ^ parse () |'(' -> incr i; add_bracket (); parse () |')' -> incr i; let u = (rem_bracket ()) in u ^ parse () | _ -> pop_all () in parse () Вот эта штука преобразует инфиксную запись в постфиксную. К сожалению, времени на более подробное объяснение уже не остаётся. Категория:Программирование